package com.bryantkobe.myspringcode.utils;

import java.util.*;

/**
 * @description: 子产品ID处理保留
 * @author: alienwarezzl
 * @date: 2025/7/6
 */
public class SonProductIdProcessor {
    // Trie节点类
    static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        boolean isEndOfWord; // 标记当前节点是否为完整ID
        boolean hasCompleteChild; // 标记子树中是否存在完整ID（包括子孙节点）
    }

    // 插入单词到Trie
    private static void insert(TrieNode root, String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            current = current.children.computeIfAbsent(c, k -> new TrieNode());
        }
        current.isEndOfWord = true;
    }

    // 在Trie中搜索节点（用于获取ID对应的节点）
    private static TrieNode searchNode(TrieNode root, String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            current = current.children.get(c);
            if (current == null) {
                return null;
            }
        }
        return current;
    }

    // 后序遍历更新hasCompleteChild字段
    private static void updateHasCompleteChild(TrieNode node) {
        if (node == null) return;

        // 递归处理子节点
        for (TrieNode child : node.children.values()) {
            updateHasCompleteChild(child);
        }

        // 更新当前节点：如果当前是完整ID或任意子节点有完整ID，则标记为true
        node.hasCompleteChild = node.isEndOfWord;
        if (!node.hasCompleteChild) {
            for (TrieNode child : node.children.values()) {
                if (child.hasCompleteChild) {
                    node.hasCompleteChild = true;
                    break;
                }
            }
        }
    }

    public static Set<String> removeParentIDs(Set<String> ids) {
        // 步骤1：处理TEMP格式，标记待移除的父ID
        Set<String> toRemove = new HashSet<>();
        for (String id : ids) {
            if (id.matches("[a-zA-Z]+") && id.endsWith("TEMP")) {
                String base = id.substring(0, id.length() - 4);
                if (ids.contains(base)) {
                    toRemove.add(base);
                }
            }
        }

        // 步骤2：构建Trie树并插入所有ID
        TrieNode root = new TrieNode();
        for (String id : ids) {
            insert(root, id);
        }

        // 步骤3：更新每个节点的hasCompleteChild字段
        updateHasCompleteChild(root);

        // 步骤4：检查每个ID是否是父产品（存在非字母开头的子产品）
        for (String id : ids) {
            if (toRemove.contains(id)) {
                continue; // 已标记移除的ID跳过检查
            }
            TrieNode node = searchNode(root, id);
            if (node == null) continue;

            // 遍历当前节点的子节点
            for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
                char c = entry.getKey();
                TrieNode childNode = entry.getValue();
                // 关键：如果子节点字符非字母且子树中有完整ID，则当前ID是父产品
                if (!Character.isLetter(c) && childNode.hasCompleteChild) {
                    toRemove.add(id);
                    break; // 找到一个子产品即可跳出
                }
            }
        }

        // 步骤5：移除所有标记的父ID
        Set<String> result = new HashSet<>(ids);
        result.removeAll(toRemove);
        return result;
    }

    public static void main(String[] args) {
        Set<String> ids = new HashSet<>();
        Collections.addAll(ids,
                "AA", "AAA", "AATEMP", "AA2023_123", "AA_456",
                "AAA_789", "BB", "INVALID_ID", "CC_TEMP","AAA_789_23","AA_789"
        );

        Set<String> filteredIds = removeParentIDs(ids);
        System.out.println("过滤后: " + filteredIds);
        /* 预期输出：
           [AATEMP, AA2023_123, AA_456, AAA_789, BB, INVALID_ID, CC_TEMP]
           解释：
           - AA被移除：因为存在AATEMP（新增格式）和AA2023_123/AA_456（原有格式）
           - AAA被移除：因为存在AAA_789（原有格式）
           - BB保留：没有子产品
           - AATEMP保留：子产品ID
           - CC_TEMP保留：不符合TEMP格式（有下划线）
        */
    }
}
